package com.lwg.datastructure.dynamicPrograming;

/**
 * @author Administrator
 * @title: test1
 * @projectName dataStructure
 * @description: TODO
 * @date 2021/10/22 002215:56
 */
public class Package {

    public static void main(String[] args) {
        System.out.println(hello());
    }

    public static int hello() {
        int packageContainWeight = 4;//包最大可装重量
        int[] weight = {1, 4, 3};//3个物品的重量
        int[] value = {150, 300, 200};//3个物品的价值
        int[][] dp = new int[value.length + 1][packageContainWeight + 1];  //定义数组的容量
        //1.循环遍历第几个物品 从1-3
        for (int i = 1; i <= value.length; i++) {
            //2.循环遍历背包的容量
            for (int j = 1; j <= packageContainWeight; j++) {
                //3.比较当前物品的重量是否满足背包的重量
                if (j >= weight[i - 1]) {  //即当前的背包能承受当前物品的重量
                    //3.得到每一行的总价值数据  如果选择当前物品则在上一行中找到剩余重量所拥有的价值+当前物品的价值，不选择当前物品则防止上一行的物品质量(因为上一行的重量肯定满足)
                    dp[i][j] = Math.max(dp[i - 1][j], value[i - 1] + dp[i - 1][j - weight[i - 1]]);
                    System.out.println(dp[i][j]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[value.length][packageContainWeight];
    }
}
